算術 (arithmetic)
Robinson 算術 (Q)
有限公理化可能
公理
$ \forall n_{\in\N}(Sn\ne 0)
$ \forall n,m_{\in\N}(Sn=Sm\to n=m)
$ \forall n_{\in\N}(n=0\lor\exist m_{\in\N}(Sm=n))
$ \forall n_{\in\N}(n+0=n)
$ \forall n,m_{\in\N}(n+Sm=S(n+m))
$ \forall n_{\in\N}(n\times 0=0)
$ \forall n,m_{\in\N}(n\times Sm=(n\times m)+n)
Presburger 算術
公理は組$ (\N,0_{\in\N},1_{\in\N},+_{:\N\times\N\to\N})を定める
$ \forall n_{\in\N}(0\ne n+1)
$ \forall n,m_{\in\N}(x+1=y+1\to x=y)
$ \forall n_{\in\N}(n+0=n)
$ \forall n,m_{\in\N}(n+(n+1)=(n+m)+1)
公理圖式$ (P(0)\land\forall n_{\in\N}(P(n)\to P(n+1)))\to\forall n_{\in\N}P(n)
n 階算術の model を$ \cal Nとし、其の理論を$ {\rm Th}({\cal N}):=\{\theta|{\cal N}\vDash\theta\}と書く。眞理述語$ T、卽ち n 階算術の文$ \thetaが妥當か否かをその Gödel 數$ \#\thetaから判定する文$ {\cal N}\vDash T(\#\theta)\iff{\cal N}\vDash\thetaが、n 階算術の文であるとしたら矛盾する$ {\rm Th}({\cal N})\cup\{T\}\vDash\bot。$ T\notin{\rm Th}({\cal N}) 初等函數算術 (EFA (elementary function arithmetic)。指數函數算術)
初等歸納的算術 (elementary recursive arithmetic。ERA)
原始歸納的算術 (primitive recursive arithmetic。PRA)
階層
算術的階層 (arithmetical hierarchy。Kleene hierarchy)$ \Sigma^0_n,$ \Pi^0_n,$ \Delta^0_n
有界量化子のみを含む Peano 算術 (PA)に等價な論理式は$ \Sigma^0_0と$ \Pi^0_0の兩方に屬する。$ \Sigma^0_0=\Pi^0_0=\Delta^0_0 論理式$ \psiが$ \Pi^0_nに屬するならば、$ \exist x_1\dots\exist x_k\psiと等價な論理式は$ \Sigma^0_{n+1}に屬する
論理式$ \psiが$ \Sigma^0_nに屬するならば、$ \forall x_1\dots\forall x_k\psiと等價な論理式は$ \Pi^0_{n+1}に屬する
$ \Sigma^0_nにも$ \Pi^0_nにも屬する論理式は$ \Delta^0_nに屬する
$ \Sigma^0_n,$ \Pi^0_n,$ \Delta^0_nに神託機械$ Aを追加した階層は$ \Sigma^{0,A}_n,$ \Pi^{0,A}_n,$ \Delta^{0,A}_nと書く
解析的階層 (analytical hierarchy)$ \Sigma^1_n,$ \Pi^1_n,$ \Delta^1_n
解析集合 (analytic set)$ {\bf \Sigma}^1_1
射影集合 (projective hierarchy)$ {\bf \Sigma}^1_n
class$ Aに class$ Bの神託機械を追加した class を$ A^Bと書く
多項式階層 (polynomial hierarchy)
$ \Delta^{\sf P}_0=\Sigma^{\sf P}_0=\Pi^{\sf P}_0:={\sf P}と定める
$ \Delta^{\sf P}_{n+1}:={\sf P}^{\Sigma^{\sf P}_n}
$ \Sigma^{\sf P}_{n+1}:={\sf NP}^{\Sigma^{\sf P}_n}
$ \Pi^{\sf P}_{n+1}:={\sf coNP}^{\Sigma^{\sf P}_n}
$ \Sigma^{\sf P}_1={\sf NP}
$ \Pi^{\sf P}_1={\sf coNP}